import java.util.Stack;

class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = (left + right)/2;
            if (target < nums[mid]){
                right = mid - 1;
            }
            if (target > nums[mid]){
                left = mid + 1;
            }
            if (target == nums[mid]){
                return mid;
            }
        }
        return -1;

    }
}
class Solution1 {
    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums,target);
        if (rightBorder - leftBorder > 1){
            return new int[]{leftBorder+1,rightBorder-1};
        }
        if (leftBorder == -1 || rightBorder == -1){
            return new int[]{-1,-1};
        }
        // if (leftBorder>rightBorder){
        //     return new int[]{-1,-1};
        // }
        return new int[]{-1,-1};

    }
    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -1;
        while (left <= right){
            int mid = left+ ((right-left)/2);
            if (nums[mid] >= target){
                right = mid - 1;
                // int leftBorder = right;
            }
            if (nums[mid] < target){
                left = mid + 1;
            }
        }
        return right;
    }
    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -1;
        while (left <= right){
            int mid = left+ ((right-left)/2);
            if (nums[mid] > target){
                right = mid - 1;

            }
            if (nums[mid] <= target){
                left = mid + 1;
                // int rightBorder = left;
            }
        }
        return left;
    }
}

 class Solution2 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);

            while (j < popA.length  && !stack.empty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }

        }

        return stack.empty();

    }
}
public class Solution0820 {
}
